package leetcode_900;

import java.util.HashMap;
import java.util.Map;

import helpclass.TreeNode;

/**
 *@author 周杨
 *ConstructBinaryTreeFromPreorderAndPostorderTraversal_889_  根据先序遍历和后续遍历 确定一棵树
 *describe:这颗树不唯一 我们用区间划分左右子树 AC 100%
 *2018年11月11日 下午6:44:19
 */
public class ConstructBinaryTreeFromPreorderAndPostorderTraversal_889_ {
	Map<Integer,Integer> map;//因为元素不重复 那么可以保存其index
	public TreeNode constructFromPrePost(int[] pre, int[] post) {
        this.map=new HashMap<Integer,Integer>();
        for(int i=0;i<post.length;++i) {
        	map.put(post[i], i);
        }
        return help(pre,post,0,post.length-1,0,post.length-1);
    }
	
	public TreeNode help(int []pre,int []post,int preLeft,int preRight,
			int postLeft,int postRight) {
		if(preLeft>preRight) return null;//必须要 如果区间不合法 那就返回空指针
		TreeNode now=new TreeNode(pre[preLeft]);//以第一个为开头
		if(preLeft==preRight)	return now;
		int index=map.get(pre[preLeft+1]);//找出post[]里 下一个左节点根的区间
		int diff=index-postLeft;//计算偏移量 也就是区间的长度
		now.left=help(pre,post,preLeft+1,preLeft+1+diff,postLeft,index);
		now.right=help(pre,post,preLeft+1+diff+1,preRight,index+1,postRight);
		return now;
	}
}
